package LC206;

/**反转链表
 *
 */
class Solution {
    //方法1
    public ListNode reverseList1(ListNode head) {
        ListNode n1 = null;
        ListNode p = head;
        while (p != null) {
            n1 = new ListNode(p.val, n1);
            p = p.next;
        }
        return n1;
    }

    //方法2
    public ListNode reverseList2(ListNode head) {
        List list1 = new List(head);
        List list2 = new List(null);
        while(true) {
            ListNode first = list1.removeFirst();
            if (first == null) {
                break;
            }
            list2.addFirst(first);
        }
        return list2.head;
    }

    static class List {
        ListNode head;

        public List(ListNode head) {
            this.head = head;
        }

        public void addFirst(ListNode first) {
            first.next = head;
            head = first;
        }

        public ListNode removeFirst() {
            ListNode first = head;
            if (first != null) {
                head = first.next;
            }
            return first;
        }
    }

    //方法3 · 递归
    public ListNode reverseList3(ListNode p) {
        if (p == null || p.next == null) {
            return p;
        }
        ListNode last = reverseList3(p.next);
        p.next.next = p;
        p.next = null;
        return last;
    }

    //方法4
    public ListNode reverseList4(ListNode head) {
        if (head == null || head.next == null) {
        return head;
        }
        ListNode n1 = head;
        ListNode o2 = head.next;
        while(o2 != null) {
            head.next = o2.next; //o2从链表断开
            o2.next = n1;  //o2指向新节点
            n1 = o2;
            o2 = head.next;
        }
        return n1;
    }

    //方法5
    public ListNode reverseList5(ListNode head) {
        ListNode o1 = head;
        if (o1 == null || o1.next == null) {
            return o1;
        }
        ListNode n1 = null;
        ListNode o2;
        while (o1 != null) {
            o2 = o1.next; //o2指向旧链表的次节点
            o1.next = n1;
            n1 = o1;
            o1 = o2;
        }
        return n1;
    }
}
